package com.ypj.community.domain;

import java.util.ArrayList;
import java.util.List;

public class LeetCode {
    public static void main(String[] args) {
        generateParenthesis(2);
    }
    public static List<String> generateParenthesis(int n) {
        if(n == 0) return new ArrayList<String>();

        //初始化dp，将dp[0]设置为[]
        List<List<String>> dp = new ArrayList<>();
        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);

        //根据dp[0]，依次计算出dp[1]、dp[2]...dp[n]
        for(int i = 1; i <= n; i++){
            List<String> temp = new ArrayList<>();
            for(int j = 0; j < i; j++){
                //i = j时所有括号的排列组合
                List<String> a = dp.get(j);
                //剩下所有括号的排列组合
                List<String> b = dp.get(i - j - 1);
                for(String str1: a){
                    for(String str2 : b){
                        //计算所有的排列组合
                        temp.add("(" + str1 + ")" + str2);
                    }
                }
            }
            dp.add(temp);
        }
        return dp.get(n);
    }

}
